nLab cumulative hierarchy

Contents

Contents

Idea

In material set theory, especially versions of set theory that accept the axiom of foundation that the membership relation \in is an extensional (but not necessarily transitive) well-founded relation, there is a picture of sets as forming a cumulative hierarchy, hierarchically ordered by a rank function valued in the ordinals. The idea is that on Day 0 the empty set is born; on Day n+1n+1 is born the power set of Day nn. On limit Days all the sets born earlier are collected together into a single set which is their union. The cumulative hierarchy picture amounts to the assertion that every set belongs to some set produced by this iterative procedure.

In ZFC

Suppose VV is a model of ZFC. Recall that in the theory ZFC, a set xx is defined to be transitive if bxb \in x implies bxb \subset x; this is the same as saying that if abxa \in b \in x then axa \in x. Note this doesn’t mean that the relation \in on the set consisting of xx and the elements of its transitive closure is itself transitive: the condition concerns only chains abca \in b \in c where c=xc = x. However, if that relation is transitive, then it is transitive, and extensional (by the extensionality axiom), and well-founded (by the axiom of foundation), and hence a well-order according to the argument here. In this case, xx is by definition an ordinal number (in the sense of von Neumann).

Letting On(V)On(V) be the class of ordinals (= ordinal numbers), one may define with the help of the replacement axiom a function

R:On(V)VR: On(V) \to V

by transfinite induction as follows: R(0)=0R(0) = 0, while

  • R(α+1)=P(R(α))R(\alpha + 1) = P(R(\alpha)) (where PP denotes power set),

  • R(β)= α<βR(α)R(\beta) = \bigcup_{\alpha \lt \beta} R(\alpha) when β\beta is a limit ordinal.

Proposition

Each of the R(α)R(\alpha) is transitive, and αβ\alpha \leq \beta implies R(α)R(β)R(\alpha) \subseteq R(\beta).

Proof

First, if XX is a transitive set, then so is P(X)P(X). For suppose AP(X)A \in P(X). Then AXA \subseteq X, and so if xAx \in A, we have xXx \in X and thus xXx \subset X since XX is transitive, so that xP(X)x \in P(X). We have thus shown AP(X)A \subset P(X).

That each R(α)R(\alpha) is transitive now follows by an easy induction.

And so R(α)R(α+1)=P(R(α))R(\alpha) \subset R(\alpha + 1) = P(R(\alpha)) since R(α)P(R(α))R(\alpha) \in P(R(\alpha)), and now αβR(α)R(β)\alpha \leq \beta \Rightarrow R(\alpha) \subseteq R(\beta) follows by an easy induction.

If xR(γ)x \in R(\gamma), then there is a least β\beta such that xR(β)x \in R(\beta), and this β\beta must be a successor ordinal, β=α+1\beta = \alpha + 1. We define the rank of xx to be that α\alpha. Thus

  • \emptyset has rank 00,

  • 1{}1 \coloneqq \{\emptyset\} has rank 11,

  • {1}\{1\} and 2{0,1}2 \coloneqq \{0, 1\} have rank 22,

and so on. Each ordinal α\alpha has rank α\alpha.

Theorem

For every element xx of VV, there is some αOn(V)\alpha \in On(V) such that xR(α)x \in R(\alpha). Thus every set xx appears as an element somewhere within the cumulative hierarchy

R(0)R(1)R(ω)R(ω+1)R(ω+ω)R(0) \subset R(1) \subset \ldots \subset R(\omega) \subset R(\omega + 1) \subset \ldots \subset R(\omega + \omega) \subset \ldots

The proof is essentially that αOn(V)R(α)\bigcup_{\alpha \in On(V)} R(\alpha) is an \in-inductive set of VV, and so must be all of VV since (V,)(V, \in) is well-founded (by the axiom of foundation). Details may be found in any reasonable text on ZFC set theory, for example Kunen.

Remark

The notation VV so widely seen in set theory texts and articles is a kind of visual pun that refers to the cumulative hierarchy: one imagines the V as outlining an angle, with a horizontal cross-section of the space inside the angle at height α\alpha suggesting a set R(α)R(\alpha), which expands as α\alpha increases; the ordinals α\alpha themselves may be pictured as vertebrae of a spine or line therein. All sets in the cumulative hierarchy lie somewhere within the V.

In algebraic set theory

The idea of the cumulative hierarchy is realized in algebraic set theory via the construction of an initial “ZF-algebra”. In broad-brush terms, there is a general connection between well-foundedness and initial algebras, as in Paul Taylor’s theory of recursion where an initial TT-algebra (for a taut functor TT) is seen as a well-founded coalgebra (X,θ:XTX)(X, \theta: X \to T X) for which θ\theta is an isomorphism (i.e., a maximal well-founded coalgebra). Algebraic set theory can be seen as exploiting this connection and working out the details in cases specific to operations on “small sets”, eventually enabling one to get at the cumulative hierarchy per se, i.e., the universe of well-founded sets (as well as the universe of ordinals, etc.).

This deserves to be discussed at length, but let us try to give a few hints for now. One starts with a pretopos 𝒞\mathcal{C} (whose objects are regarded as “classes”) equipped with a suitable notion of “smallness”: to say a map f:EXf: E \to X in the pretopos is “small” means intuitively that all its fibers are “small” (i.e., sets). Thus one assumes some reasonable axioms on the class of small maps in 𝒞\mathcal{C}, including the existence of a universal small map “elel”: EUE \to U, with the elements uu of UU naming small sets and the fiber over uu the actual (small) set of its elements. The smallness axioms allow one to construct a small-power set functor P s:𝒞𝒞P_s: \mathcal{C} \to \mathcal{C}; intuitively this sends a class CC to the class of small subsets of CC. This carries a monad structure whose algebras (X,sup:P sXX)(X, \sup: P_s X \to X) are “small-complete” posets in 𝒞\mathcal{C}.

To get at the actual cumulative hierarchy (with attendant global membership relation \in), one defines a ZF-algebra to be a small-complete poset (V,)(V, \leq) in 𝒞\mathcal{C}, equipped with a function s:VVs: V \to V satisfying suitable conditions; here one is to think of \leq as “inclusion” and s(x)s(x) as a singleton {x}\{x\}. The relation xyx \in y can then be interpreted as s(x)ys(x) \leq y. The initial object in the category of ZF-algebras then captures the desired universe of well-founded sets.

Remark

The details of the construction of the initial ZF-algebra should be examined with attention to connections with Taylor’s theory of well-founded coalgebras; for example, systematic use is made of bisimulations which has a general meaning in coalgebra theory.

This program, initiated by André Joyal and Ieke Moerdijk, permits a fine-grained analysis of intuitionistic ZF-set theory and intuitionistic ordinals. The reader is referred to their monograph for details, and to the Algebraic Set Theory page for further pointers to the literature.

References

The cumulative hierarchy made its first appearance in

  • D. Mirimanoff, Les antinomies de Russell et de Burali-Forti et le problème fondamental de la théorie des ensembles , L’enseignement Mathématique 19 (1917) pp.37-52. (pdf; 19,4MB)

Another historically important contribution is

  • Dana Scott, Axiomatizing Set Theory , pp.207-214 in Axiomatic Set Theory - Proc. Symp. Pure Math. 13, AMS Providence 1974.

A modern textbook account can be found e.g. in

  • Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics Vol. 102 (2006), Elsevier.

For algebraic set theory consult the following monograph

  • André Joyal and Ieke Moerdijk, Algebraic Set Theory, London Math. Soc. Lecture Series Notes 220 (1995), Cambridge University Press.

Last revised on April 10, 2019 at 16:00:21. See the history of this page for a list of all contributions to it.